COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\init{
C00003 00003	\chapbegin{3}		% Here beginneth Chapter 3
C00006 00004	\sectionbegin[1]{AM'S SEARCH}\par
C00018 00005	\sectionbegin[2]{CONSTRAINING AM'S SEARCH}\par
C00025 00006	\sectionbegin[3]{THE AGENDA}\par
C00026 00007	 \subsectionbegin[3.1]{Why an Agenda?}
C00031 00008	 \subsectionbegin[3.2]{Details of the Agenda Scheme}
C00038 ENDMK
C⊗;
\init{
\input cmpdes
\input ammacs
\def\draft{T}
\titlepage
\newpage
\setcount0 27
\parttitle{AM: DISCOVERY IN MATHEMATICS AS HEURISTIC SEARCH}
}
\baselineskip 12pt
\chapbegin{3}		% Here beginneth Chapter 3
\chaptertitle{AGENDA}
\rjustline{\:B Agenda}
\vskip 14pc

\epigraph{`Objectively' given, `important' problems may arise [in math].
But even then the mathematician
is essentially free to take it or leave it and turn to something else, while
an `important' problem in [any other science] is usually a conflict, a contradiction,
which `must' be resolved. The mathematician has a wide choice of which way to turn,
and he enjoys a very considerable freedom in what he does.}
\author{von Neumann}
\epigraphend


Section 3--1 will give the  reader a feeling for the  immensity
of {\AM}'s search space. This is the ``problem.''  The next section will give the
top-level ``solution'':  the flow of control is  governed by a job-list,
an agenda of plausible tasks.   Section 3--3 will present  some
details of this global control scheme.
Chapter 4 deals with  the way {\AM}'s heuristics operate; this
could be  viewed as the ``low-level'' or {\sl local} control structure of
{\AM}.  

\sectionskip
\sectionbegin[1]{AM'S SEARCH}\par

\epigraph{To develop mathematics, one must always labor to substitute ideas for
calculations.}
\author{Dirichlet}
\epigraphend

\noindent\!
Let's first spend a paragraph reviewing how  concepts are stored.  {\AM}
contains a collection  of data structures, called {\sl concepts}.  Each
concept is meant to  coincide intuitively with one mathematical  idea
(\eg,  Sets, Union,  Trichotomy).   As such,  a concept  has several
aspects  or  parts, called  {\sl facets} (\eg,  Examples, Definitions,
Domain/range, Worth).    If you  wish  to think  of  a concept  as  a
``frame,'' then its facets are  ``slots'' to be filled in.  Each facet of
a concept will either be totally blank, or else will contain a  bunch
of {\sl entries}.   For example,  the Algorithms  facet of the  concept
Union may  point to several equivalent LISP  functions, each of which
can be used to  form the union of two  \ffootnote{sets.}{The reasons for  having
multiple algorithms is that sometimes {\AM}  will want one that is fast,
sometimes  {\AM} will  be  more concerned  with economizing  on storage,
sometimes {\AM}  will  want  to ``analyze''  an  algorithm.  For  these reasons
it  must be a very  unoptimized function.}  Even the
``heuristic rules'' are merely entries on the appropriate kind of facet
(\eg, the entries on the Interest facet of the Structure concept are
rules for judging  the interestingness of \footnote{Structures).}{A typical such
rule is: ``{\sl A  structure is very  interesting if  all its elements  are
mildly interesting in precisely the same way.}'' }

At any moment,  {\AM} contains a couple hundred concepts,  each of which
has  only  {\sl some} of  its facets  filled in.    {\AM} starts  with 115
concepts, and  grows  to about  300 concepts  before  running out  of
time/space.   Most facets of most  concepts are totally  blank.  {\AM}'s
basic activity is to select some facet of some concept, and then  try
to fill in some  entries for that \footnote{slot.}{This is  not quite complete.
In addition to  filling in entries for a given facet/concept pair, {\AM}
may wish to check  it, split it up, reorganize  it, etc. }  Thus  the
primitive kind  of {\sl task}  for {\AM}  is to  deal with  a particular
facet/concept pair.  A typical task looks like this:

\yskip
\hbox{\hfill\inbox{\inbox{\hbox{\bf Check  the 
entries  on the  ``Domain/range'' facet of  the ``Bag-Insert''
concept}}}\hfill}
\yskip

If the average concept has ten or twenty blank  facets, and there are
a  couple  hundred  concepts,   then  clearly  there  will  be  about
$20\times200=4000$ ``fill-in'' type tasks for {\AM} to work on at any given
moment.   If several  hundred facets  have recently  been filled  in,
there  will be that  many ``check-entries''  type tasks available.   
Executing a task happens to take around ten or twenty cpu seconds,
so over the course of a few hours
only a small percentage of these  tasks can ever be \footnote{executed.}{The precise
``18 seconds average''
figure is not important. All heuristic-search programs suffer this same
handicap: as the depth to which they've searched increases, the percentage of
nodes (at or above that level) which have been examined {\sl decreases}
exponentially (assuming the branching factor $b$ is strictly larger than unity).}

Since most of these tasks  will never be explored, what will  make {\AM}
appear smart---or stupid---are its choices of which task to pick at
each \footnote{moment.}{This is true of all heuristic search programs.
The branchier the search, the more it applies.}\!
So it's worth {\AM} spending a nontrivial amount of time
deciding which task to execute next. On the other hand, it had better
not be {\sl too} much time, since a task does take only a dozen
\ffootnote{seconds.}{The answer is that {\AM} spends this ``deciding'' time not
just before a task is {\sl picked}, but rather each time a task is added to
the agenda. A little under 1 cpu second  is spent, on the average, to place the
task properly on the agenda, to assign it a meaningful numeric priority value. 
So ``action time'' is roughly one order of magnitude larger than
``deciding time.'' }

One question that  must be answered is: What percentage of {\AM}'s legal
moves  (at  any  typical  moment)  would  be  considered  intelligent
choices, and what  percentage would be irrational?   The answer comes
from empirical results.  The percentages vary wildly depending on the
previous few tasks.  Sometimes, {\AM} will be obviously  ``in the middle''
of a sequence of tasks, and  only one or two of the legal tasks would
seem plausible.  Other times, {\AM} has just completed an  investigation
by running  into dead-ends,  and there  may be  hundreds of tasks  it
could  choose and not be  criticized.  The median  case would perhaps
permit about six of the legal tasks to be judged reasonable.

It is important  for {\AM}  to locate one  of these  currently-plausible
tasks,  but it's  not  worth  spending much  time  deciding which  of
{\sl them} to  work on next.  {\AM} still faces a huge search: find one of
the six winners out of a few thousand candidates.

Its choice of tasks is made even more important  due to the 10-second
``cycle time''---the time to  investigate/execute one task.   A human
user is watching, and ten seconds  is a nontrivial amount of time  to
a person.  The user can therefore observe, perceive,  and analyze each and every
task that  {\AM} selects.  Even just a  few bizarre choices will greatly
lower the user's opinion of {\AM}'s intelligence.  The trace of {\AM}'s actions is
what counts,  not its final  results.  So {\AM}  can't draw much  of its
apparent intelligence from the {\sl speed} of the computer.

Chess-playing programs  have had to face the dilemma of the trade-off
between  ``intelligence'' (foresight,  inference,  processing, etc.)  and
total  number   of  board  situations   examined.    In   chess,  the
characteristics of current-day  machines, language power {\it vs.} speed,
and (to some extent) the limitations of our understanding of how to be
sophisticated,
have  to date  unfortunately
still favored fast,  \footnote{nearly-blind}{That is, using a very  simple static
evaluation  function.}  search.   Although machine speed and LISP slowness
may allow
blind search to win over symbolic inference for {\sl shallow} searches,
it can't  provide any  more than  a constant  speed-up factor  for an
exponential search. Inference is slowly gaining on brute \footnote{force,}{For
example, see Berliner[74]. There, searching is used mainly to verify plausible
moves (a convergent process), 
not to discover them (a bushier search).} and must someday triumph.

Since  the number  of ``legal moves''  for {\AM} at  any moment  is in the
thousands, it  is unrealistic  to  consider \footnote{``systematically''}{For
example, exhaustively, or  using $\alpha\beta$ minimaxing,
etc.} walking through the
entire space that {\AM} can reach.  In {\AM}'s problem domain, there is  so
much ``freedom'' that  symbolic inference finally {\sl can} win  over the
``simple  but  fast''  exploration  \footnote{strategy.}{This  is  the  author's
opinion, partially  supported  by the  results  of  {\AM}.   Paul  Cohen
disagrees,  feeling  that machine  speed  should  be  the key  to  an
automated mathematician's success.}

\sectionskip
\sectionbegin[2]{CONSTRAINING AM'S SEARCH}\par

\epigraph{There exist too many combinations to consider all
combinations of existing entities;
the creative mind must only {\sl propose} those of potential interest.}
\author{Poincar\'e}
\epigraphend

\noindent A great  deal of  heuristic  knowledge is  required to  constrain  the
necessary processing effectively,  to zero  in on  a good  task to  tackle
next.  This is done in two stages:\par

\listbegin
\numlistentry[1]{A list of plausible facet/concept pairs is maintained. Nothing can
get onto  this list unless there  is some reason why  filling in (or checking) that
facet of that concept would be worthwhile.}

\numlistentry[2]{All the plausible tasks on this ``job list'' are ranked by the
number and strength of  the different reasons supporting them.   Thus
the facet/concept  pairs near the  top of the  list will all  be very
promising tasks to work on.}
\listend

The first of these constraints is akin to replacing a {\sl legal}  move
generator by  a {\sl plausible}  move generator.   The  second kind  of
constraint is akin to using a heuristic evaluation function to select
the best move from among the plausible ones.\ffnote{Past AI programs
(\eg, [Samuel 67]) have indicated that
constraining generation (stage 1, above) is more important than sophisticated
ordering of the resultant candidates (stage 2).
This was confirmed by the experiments performed on {\AM}. }

The job-list or {\sl agenda} is a data structure which is a natural way
to store the  results of these procedures.   It is  a  list of all
the  plausible tasks which  have been  generated, and   it is kept
ordered by the  numeric estimate  of how worthwhile  each task is.  A
typical entry on the agenda might look like this:

\vskip \listskip

{\eightpoint \:>  \parskip 1pt \lineskip 1pt \parindent 0pt
     \hbox{\ \ \       Fill in  the  EXAMPLES  facet of the  PRIMES  concept }
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$   {\it Reasons for filling in this facet}}
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\↓$ }
\par\hangindent 30pt for 1 {\bf  1. No examples of primes are known so far.}
\par\hangindent 30pt for 1 {\bf  2. Focus of attention: {\AM} just defined Primes.}
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$\ {\it Overall value of these reasons}}
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\|$ }
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\↓$ }
\par \hbox{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\bf 250}}

}

\vskip \listskip
\tenpoint \parindent 20pt

While the  top  task is  being executed,  some  new tasks  might  get
proposed and  merged into the agenda.  Also,  some new concepts might
get created, and this, too, would generate a flurry of new tasks.

After  {\AM} stops  filling in  entries for  the facet  specified in the
chosen  task, it removes that  task from the agenda,  and moves on to
work on whichever task is the highest-rated at that time.

The reader probably has a dozen good questions in mind
at this point (\eg, How do  the reasons get rated?  How do the  tasks
get proposed?  What  happens after a task is selected?).   The next
section  should answer most  of these. Some more  judgmental ones (How
dare you propose a numeric calculus of plausible reasoning!   If you
slightly  de-tune all  those numbers,  does the  system's performance
fall apart?) will be answered in Chapter 7.

\sectionskip
\sectionbegin[3]{THE AGENDA}\par

\epigraph{Creative energy is used mainly to ask the right question.}
\author{Halmos}
\epigraphend

\vskip -18pt
 \subsectionbegin[3.1]{Why an Agenda?}
This subsection provides motivation for the following one, by arguing
that  a job-list scheme is  a natural mechanism to  use to manage the
task-selection problem {\AM} faces. 

Recall  that {\AM} must zero in on  one
of the best  few tasks to perform next, and  it repeatedly makes this
choice.   At each moment,  there might be  thousands of directions to
explore (plausible tasks to consider).

If all the legal tasks were written out, and  reasons were thought up
to support each one, then perhaps we could order them by the strength
of those reasons, and  thereby settle on the  ``best'' task to work  on
next.   In  order to  appear ``smart''  to  the human  user, {\AM}  should
{\sl never} execute a task having no reasons attached.

For the moment, assume some magical function exists, which provides
a numeric rating, a priority value,  for any given task.  The  function
looks  at a  given facet/concept  pair, examines  all the  associated
reasons supporting that task, and computes an estimate of how worthwhile it would be
for {\AM} to spend some time now working on that facet of that concept.

So {\AM} will maintain a list of those legal tasks  which have some good
reasons  tacked onto  them,  which justify  why each  task  should be
executed, why it is plausible.  At least implicitly, {\AM} has a numeric
rating for each task. 

Give or take  a few features, this notion of  a job-list is the one
which {\AM}  uses. It  is  also called  an \ffootnote{{\sl agenda}.}{Borrowed from
Kaplan's term for the job-list present in  KRL0 (see
Bobrow & Winograd[77]). For an earlier general discussion of agendas,
see Knuth[68].}
``A task on the  agenda'' is the same as ``a job on the job-list'' is the
same as ``a facet/concept pair which has been proposed'' is the same as
``an  active node  in the  search space.''   Henceforth,  I'll use  the
following  all interchangeably:  task, facet/concept  pair, node, 
\footnote{job.}{Each of these terms  will conjure up a
slightly different image: a ``job'' is something to do, a ``node'' is  an
item in  a  search space,  ``facet/concept pair''  reminds  you of  the
format of a task.}

The flavor of agenda-list used here is analogous to the control structure of
HEARSAY-II [Lesser {\etal} 75]. Vast numbers of tasks are
proposed and added to the job-list. Occasionally, when some new data arrive,
some task is repositioned.

 \subsectionbegin[3.2]{Details of the Agenda Scheme}
At each moment, {\AM} has many plausible tasks  (hundreds or even thousands) which
have  been  suggested for  some  good reason or  other,  but  haven't been
carried out yet.  Each task is  at the level of working on a  certain
facet of a certain concept: filling  it in, checking it, etc.  Recall
that  each task also  has tacked onto  it a list  of symbolic reasons
explaining why the task is worth doing.


In addition,  a  number (between  0  and 1000)  is attached {\sl to each
reason}, representing some  absolute  measure of  the  value of  that
reason (at the moment).  One global \ffootnote{formula}{Here is that  formula:
$Worth(J) =  \|\sqrt{\Sigma R↓i↑2}\| \times  (0.2\times Worth(A)\  +
0.3\times Worth(F)\ + 0.5\times Worth(C))$,  where J =  job to  be judged =  (Act A,
Facet F,  Concept  C),  and $\{R↓i\}$  are  the ratings  of  the  reasons
supporting J.   For  the sample  job pictured  in the  box below, A=FillIn,
F=Examples,  C=Sets, $\{R↓i\}=\{100,100,200\}$. The formula will be
repeated---and explained---in Section 4--3.}  combines 
all the reasons' values  into a single priority
value for the task as a whole.
This overall rating is taken to indicate how worthwhile it would be for
{\AM} to bother executing that task, how interesting the task 
would probably turn out to be.
The ``intelligence'' of {\AM}'s selection of task is thus seen
to depend on this one formula.  Yet experiments show
that its precise form is not important. We conclude
that  the  ``intelligence''  has  been  pushed  down  into the  careful
assigning of reasons (and {\sl their} values) for each proposed task.

A typical entry on the agenda might look like this:\par

\yyskip
{\eightpoint \:>  \parskip 1pt \lineskip 1pt \parindent 0pt
     \hbox{\ \ \       TASK: Fill-in examples of Sets }
\par \hbox{\ \ \       PRIORITY: 300 }
\par \hbox{\ \ \       REASONS: }
\par \hbox{\ \ \ \ \ \ \ \  100: No known examples for Sets so far. }
\par \hbox{\ \ \ \ \ \ \ \  100: Failed to fillin examples of Set-union, for lack of examples of Sets }
\par \hbox{\ \ \ \ \ \ \ \  200: Focus of attention: {\AM} recently worked on the concept of Set-union }

}
\yyskip

\tenpoint \parindent 20pt
\noindent\!
Notice the similarity of this to the initial few lines which {\AM} types
just after it selects a job to work on.

The priority value of a task serves a dual purpose:  first, it
is used to determine which task on the agenda is the most promising
one to work on next.  Second, once a task has been chosen, that
task's priority value 
then is used as an estimate of how  much time and space it deserves. The
sample task above might rate 20 cpu seconds and 200 list cells. When
either of these resources is used up, {\AM} terminates work on the
task, and  proceeds to pick  a new  one.  
These two limits will be referred to henceforth as {\sl time/space quanta}
which are allocated to the chosen task.
Whenever several techniques exist for satisfying some task, the remaining
time/space quanta are divided evenly among those alternatives; \ie, each
method is tried for a small time. This policy of parceling out time and
space quanta is called ``activation energy'' in [Hewitt 76] and called
``resource-limited processes'' in [Norman & Bobrow 75].
In  the case of  filling in
examples of sets, the space quantum (200 cells) will be used up quickly
(long before the 20 seconds expire).

\yskip

There are two big questions now:

\listbegin

\bullistentry{Exactly how is a task proposed and ranked?}
\vskip -14pt
\indlistbegin\ninepoint
\indentedline[60pt]{How is a plausible new task first formulated?}
\indentedline[60pt]{How do the supporting reasons for the task get assigned?}
\indentedline[60pt]{How does each reason get assigned an absolute numeric rating?}
\indentedline[60pt]{Does a task's priority value change? When and how?}
\indlistend\tenpoint
\vskip -14pt
\bullistentry{How does {\AM} execute a task, once it's chosen?}
\vskip -14pt
\indlistbegin\ninepoint
\indentedline[60pt]{Exactly what can be done during a task's execution?}
\indlistend\tenpoint
\vskip -14pt
\listend

\noindent {The next chapter will deal with both of these questions.}

\worldend